Because of its computational simplicity, small channel capacity usage, reduced memory demand and rapid response to topological changes, some form of single-shortest-path (e.g. Bellman-Ford, ARPANET) selection scheme is typically employed for routing digital data traffic among member stations (nodes) of a multinode packet-switched communications network to destination. A major shortcoming of a single-shortest-path approach, however, is its failure to achieve optimal delay or throughput performance (minimum average delay and maximum throughput) during steady-state operation. This inadequacy results from the fact that, in a general multi-node network, optimal routing requires a splitting of the data flow (i.e. different packets from a given data source may travel along respectively different routes to a given destination).
In an effort to satisfy this requirement and take advantage of the substantial capacity of the network that goes unused in a single-shortest-path approach, there has been proposed an optimal steady state performance mechanism (in terms of minimum average delay and maximum possible throughput), known as the Gallager algorithm (described in an article entitled "A Minimum Delay Routing Algorithm Using Distributed Computation" by R. G. Gallager, IEEE Transactions on Communications, Vol. COM-25, Jan. 1977, pp 73-85), in which multiple paths through the network are employed, by subdividing flow into subportions that are routed over a number of different source-to-destination highways. In the Gallager scheme, routing variables are varied incrementally in accordance with control packets which propagate through the network, the control packets being based upon a link metric, which is the derivative of the delay with respect to traffic flow over a link.
This need to estimate the derivative of link delay is a principal obstacle to realizing a practical implementation of the Gallager approach. An estimate of the link delay could be based upon the output queue length (packets awaiting transmission at a node) and the known (or estimated) propagation delay. However, such an estimate would be noisy due to the varying queue length, and would therefor require a substantial amount of averaging (low-pass filtering) in order to obtain a reliable estimate. Estimating the derivative of the delay would require even more averaging, in order to filter the very noisy raw estimates. Indeed, because it is highly questionable whether sufficiently reliable estimates of the derivative of the link delay can obtained within a reasonable computation window, the practical application of the Gallager approach to an operational network is severely limited. Additional drawbacks of the Gallager mechanism include its computational complexity, its usage of a large portion of available channel capacity, the need to select a step size that is based upon network topology and traffic load, and its rather slow convergence to steady state.